package club.xiaojiawei.array;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/17 19:41
 * @question 367.有效的完全平方
 * @description 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。进阶：不要 使用任何内置的库函数，如  sqrt 。
 */
public class EffectiveCompleteSquare367 {

    public static void main(String[] args) {
        System.out.println(isPerfectSquare(100));
    }

    /**
     * 二分法
     * @param num
     * @return
     */
    public static boolean isPerfectSquare(int num) {
        int size = (Integer.toString(num).length() + 2 - 1) >> 1;
        int left, right = 1;
        for (int i = 0; i < size; i++) {
            right *= 10;
        }
        left = right / 10;
        int middle;
        long temp;
        while (left <= right){
            middle = (left + right) >> 1;
            if ((temp = (long) middle * middle) > (long)num){
                if ((long) (middle - 1) * (middle - 1) < (long)num){
                    return false;
                }
                right = middle - 1;
            }else if (temp < (long)num){
                if ((long) (middle + 1) * (middle + 1) > (long)num){
                    return false;
                }
                left = middle + 1;
            }else {
                return true;
            }
        }
        return true;
    }

    /**
     * 牛顿迭代法
     * @param num
     * @return
     */
    public static boolean isPerfectSquare2(int num) {
        double x0 = num;
        while (true) {
            double x1 = (x0 + num / x0) / 2;
            if (x0 - x1 < 1e-6) {
                break;
            }
            x0 = x1;
        }
        int x = (int) x0;
        return x * x == num;
    }
}
